package com.s12.graph;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 无向图
 */
public class MyGraph {
	/**
	 * 图的顶点总个数
	 */
	private int vertexCount;

	/**
	 * 邻接表
	 */
	private LinkedList<Integer>[] adjacencyListArray;

	@SuppressWarnings("unchecked")
	public MyGraph(int vertexCount) {
		this.vertexCount = vertexCount;
		adjacencyListArray = new LinkedList[vertexCount];
		for (int i = 0; i < vertexCount; i++) {
			adjacencyListArray[i] = new LinkedList<>();
		}
	}
	
	// 无向图一条边存两次
	public void addEdge(int s, int t) {
		adjacencyListArray[s].add(t);
		adjacencyListArray[t].add(s);
	}

	public static void main(String[] args) {
		MyGraph graph = new MyGraph(8);
		graph.addEdge(0, 1);
		graph.addEdge(1, 2);
		
		graph.addEdge(3, 4);
		graph.addEdge(3, 5);
		
		graph.addEdge(6, 7);

		graph.addEdge(0, 3);
		graph.addEdge(1, 4);
		graph.addEdge(2, 5);
		
		graph.addEdge(4, 6);
		graph.addEdge(5, 7);

		graph.bfs(0, 6);
		
		graph.dfs(0, 6);
	}

	/**
	 * 广度优先搜索（Breadth-First-Search），我们平常都简称 BFS
	 * 
	 * @param start 表示起始顶点
	 * @param end 表示终止顶点. 我们搜索一条从 s 到 t 的路径
	 */
	public void bfs(int start, int end) {
		System.out.println("bfs");
		if (start == end) {
			return;
		}
		
		boolean[] visited = new boolean[this.vertexCount];
		// 初始化 prev 数组
		int[] prev = new int[this.vertexCount];
		for (int i = 0; i < vertexCount; ++i) {
			prev[i] = -1;
		}
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(start);
		visited[start] = true;

		while(!queue.isEmpty()) {
			Integer data = queue.poll();
			System.out.println("一层循环开始 " + data + " 出队");
			LinkedList<Integer> adjacencyList = this.adjacencyListArray[data];
			for (int i : adjacencyList) {
				if (!visited[i]) {
					prev[i] = data;
					if (i == end) {
						print1(prev, start , end);
						return;
					}
					visited[i] = true;
					System.out.println(i + " 入队");
					queue.add(i);
				}
			}
			System.out.println("一层循环结束");
		}
	}
	
	// 打印 s->t 的路径 方式一
	private void print1(int[] prev, int s, int t) {
		// 模拟栈
	    Stack<Integer> stack = new Stack<>();
		while (t > -1) {
			stack.push(t);
			t = prev[t];
		}
		
		while (!stack.isEmpty()) {
			System.out.print(stack.pop() + " ");
		}
		System.out.println();
	}
	
	// 打印 s->t 的路径 方式二：递归方式
	private void print2(int[] prev, int s, int t) {
		if (prev[t] > -1 && s != t) {
			print2(prev, s , prev[t]);
		}
		System.out.print(t + " ");
	}
	
	/**
	 * 深度度优先搜索（Depth-First-Search），我们平常都简称 DFS
	 * 
	 * @param s 表示起始顶点
	 * @param t 表示终止顶点. 我们搜索一条从 s 到 t 的路径
	 */
	public void dfs(int s, int t) {
		System.out.println("dfs");
		if (s == t) {
			return;
		}
		
		boolean[] visited = new boolean[this.vertexCount];
		int[] prev = new int[this.vertexCount];
		for (int i = 0; i < vertexCount; ++i) {
			prev[i] = -1;
		}
		recurDfs(s, t, visited, prev);
		print2(prev, s, t);
	}
	
	boolean found = false; // 全局变量或者类成员变量

	private void recurDfs(int w, int t, boolean[] visited, int[] prev) {
		if (found) {
			return;
		}
		
		if (w == t) {
			found = true;
			return;
		}
		
		visited[w] = true;
		LinkedList<Integer> adjacencyList = this.adjacencyListArray[w];
		for (int i : adjacencyList) {
			if (!visited[i]) {
				prev[i] = w;
				recurDfs(i, t, visited, prev);
			}
		}
	}


}
